# LRU算法
"""
LRU是一种缓存淘汰算法（在OS中也叫内存换页算法），由于缓存空间是有限的，
所以要淘汰缓存中不常用的数据，留下常用的数据，达到缓存效率的最大化。
LRU就是这样一种决定“淘汰谁留下谁”的算法，LRU是Least recently used的缩写，
从字面意思“最近最少使用”，我们就可以理解LRU的淘汰规则。
"""


# LRU的淘汰逻辑
"""
1)有新数据（意味着数据之前没有被缓存过）时，加入到列表头
2)缓存到达最大容量时，需要淘汰数据多出来的数据，此时淘汰列表尾部的数据
3)当缓存中有数据被命中，则将数据移动到列表头部（相当于新加入缓存）
按上面的逻辑我们可以看到，一个数据如果经常被访问就会不断地被移动到列表头部，
不会被淘汰出缓存，而越不经常访问的数据，越容易被挤出缓存。
"""


# 实现(OrderedDict， 双链表)
"""
首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，
另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。
注：get 和 put 方法必须都是 O(1) 的时间复杂度
注：为什么要使用OrderedDict？
缓存内部我们只需要有一个列表（list）就可以实现LRU逻辑，不过用列表虽然能实现逻辑，但是在判断是否命中缓存时，
速度可能非常慢。所以我们需要一种既能排序，又是基于hash存储的数据结构
而在Python的collections包中，已经内置了这种实用的结构OrderedDict，OrderedDict是dict的子类，但是存储在
内部的元素是有序的（列表的特点）。
"""
import collections


# OrderedDict实现LRU算法
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = collections.OrderedDict()

    def get(self, key):
        if key not in self.queue:
            return -1
        value = self.queue.pop(key)
        self.queue[key] = value
        return self.queue[key]

    def put(self, key, value):
        if key in self.queue:
            self.queue.pop(key)
        elif len(self.queue) == self.capacity:
            self.queue.popitem(last=False)
        self.queue[key] = value

    def __repr__(self):

        return str(self.queue.items())


# 双链表实现LRU算法
class DbWayNode:
    def __init__(self, key, value, pre_node=None, next_node=None):
        self.key = key
        self.data = value
        self.pre = pre_node
        self.next = next_node

    def __repr__(self):
        return f'{self.key}: {self.data}'


class DbWayLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_index(self, new_node: DbWayNode):
        pre = new_node.pre
        next = new_node.next
        if pre:
            pre.next = next
        if next:
            next.pre = pre
        new_node.pre = None
        new_node.next = self.head
        if self.head:
            self.head.pre = new_node
        self.head = new_node
        if not self.tail:
            self.tail = self.head

    def delete_last(self):
        node = self.tail
        self.tail = self.tail.pre
        self.tail.next = None
        if not self.tail:
            self.head = self.tail
        return node

    def find_value(self, value: DbWayNode):
        pre = value.pre
        if pre is not None:
            pre.next = value.next
            if not pre.next:
                self.tail = pre
            else:
                self.tail = pre.next
            self.insert_index(value)

    def __repr__(self):
        arr = []
        head = self.head
        while head:
            arr.append(str(head.data))
            head = head.next
        return "->".join(arr)


class LRUCache2:
    def __init__(self, capacity):
        self.list = DbWayLinkedList()
        self.capacity = capacity
        self.map = {}

    def get(self, key):
        if key not in self.map.keys():
            return -1
        value = self.map.pop(key)
        self.map[key] = value
        self.list.find_value(value)
        return value.data

    def put(self, key, value):
        if key not in self.map.keys():
            if len(self.map) == self.capacity:
                node = self.list.delete_last()
                self.map.pop(node.key)
            new_node = DbWayNode(key, value)
            self.map[key] = new_node
            self.list.insert_index(new_node)
        else:
            node = self.map.pop(key)
            self.map[key] = node
            if value != node.data:
                node.data = value
            self.list.find_value(node)

    def __repr__(self):
        print(self.map)
        return self.list.__repr__()


if __name__ == '__main__':
    lru = LRUCache(3)
    lru.put(1, 1)
    print(lru)
    lru.put(2, 2)
    print(lru)
    print(lru.get(1))
    print(lru)
    lru.put(3, 3)
    print(lru)
    lru.put(1, 100)
    print(lru)
    lru.put(4, 4)
    print(lru)
    print(lru.get(1))
    print(lru)
    print(lru.get(1000))

    print('#' * 15)

    lru2 = LRUCache2(3)
    lru2.put(1, 100)
    print(lru2)
    lru2.put(2, 200)
    print(lru2)
    print(lru2.get(1))
    print(lru2)
    lru2.put(3, 300)
    print(lru2)
    lru2.put(1, 100)
    print(lru2)
    lru2.put(4, 400)
    print(lru2)
    print(lru2.get(1))
    print(lru2)
    print(lru2.get(1000))
